package com.tree.sort;

/**
 * @ClassName com.tree.sort
 * Description: <类功能描述>.
 * <br>
 * @Author frankzsliu
 * @Date 2024/2/4 23:42
 * @Version 1.0
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        int target = 10;
        System.out.println(BinarySearch.binarySearch(nums,target));
    }

    /**
     * 二分查找通用规律(固定模板解决寻找>=, >, <, <=)
     * 范围查询规律
     * 初始化:
     *   int left = 0;
     *   int right = nums.length - 1;
     * 循环条件
     *   left <= right
     * 右边取值
     *   right = mid - 1
     * 左边取值
     *   left = mid + 1
     * 查询条件
     *   >= target值, 则 nums[mid] >= target时, 都减right = mid - 1
     *   >  target值, 则 nums[mid] >  target时, 都减right = mid - 1
     *   <= target值, 则 nums[mid] <= target时, 都加left = mid + 1
     *   <  target值, 则 nums[mid] <  target时, 都加left = mid + 1
     * 结果
     *   求大于(含等于), 返回left
     *   求小于(含等于), 返回right
     * 核心思想: 要找某个值, 则查找时遇到该值时, 当前指针(例如right指针)要错过它, 让另外一个指针(left指针)跨过他(体现在left <= right中的=号), 则找到了
     */
    public static int binarySearch(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        while (left <= right){
            //值得注意的是，由于 left 和 right 都是整数， 因此i+j 可能超出int类型的取值范围
            // 为了避免大数越界，我们通常采用公式 mid = i+(j-i)/2
            int mid = (left+right)/2;
            //大于target
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else {
                return  mid;
            }
        }
        return -1;
    }
}
